As computer programming has become more sophisticated, greater performance demands are placed upon basic logic combinatoral networks such as adders, multipliers, and the like. In general, these demands have been met by utilizing state-of-the-art transistor processing techniques to reduce switching delays. However, as the number of bits to be logically synthesized increases, this solution becomes inadequate. Accordingly, renewed emphasis has been placed upon the design of these basic logic networks.
One design factor that has received particular attention is the reduction of delays caused by wait states that naturally occur within the logic synthesis algorithm. For example, in a conventional adder, the final sum bit for a given pair of bits to be added is generated by combining the preliminary sum bit with the carry bit from the preceding bit pair. If a designer were to optimize the speed of the portion of the logic that generates the preliminary sum bit, the effort would be wasted if the logic has to wait for generation of the carry bit in order to generate the final sum.
Accordingly, several designs have been proposed in which the logic does not have to wait for the generation of the carry bit for each bit pair in order to generate the final sums. In U.S. Pat. No. 4,573,137, entitled "Adder Circuit," issued Feb. 25, 1986 to Ohhashi and assigned to Toshiba, two dummy sum terms are generated for each pair of bits to be added. The first dummy sum is generated assuming a carry in of 0, and the second dummy sum is generated assuming a carry in of 1. The actual carry-in signal is then used to select between the two dummy sums. Thus, rather than waiting to generate the sum terms until the carry is received, in this patent dummy sums are generated and selected by the carry-in from the preceding bit pair. This reduces the above-discussed wait time.
Another way of reducing the delays produced by wait states is disclosed in U.S. Pat. No. 4,707,800, entitled "Adder/Subtractor For Variable Length Numbers," issued Nov. 17, 1987 to Montrone et al and assigned to Raytheon Co. In this patent, the carry-in from one pair of bits is used to select the carrys for a plurality of other pairs of bits. For the least significan bit pair, the carry-out is generated. For the next most significant bit pair, a first dummy carry-out is generated assuming a carry-in of 1, and a second dummy carry-out is generated assuming a carry-in of 0. These dummy carry signals are then fed to the dummy carry generators for the next most significant pair of bits to be added, and so on, such that all the dummy carrys are predicated upon the state of the carry-out from the least significant bit pair. The actual carry-out from the least significant bit pair is then used to select the correct dummy carry-out for each bit pair. The selected dummy carry is then combined with the preliminary sum term for each bit pair to generate the final sum term for each bit pair.
Other techniques for reducing wait states are shown in U.S. Pat. No. 4,763,295, entitled "Carry Circuit Suitable For A High-Speed Arithemtic Operation," issued Aug. 9, 1988 to Yamada et al and assigned to NEC Co. (use of selection to increase efficiency in a carry look ahead scheme), and in an article by Freemen, entitled "Checked Carry Select Adder," IBM Technical Disclosure Bulletin, Vol. 13, No. 6, Nov. 1970 pp. 1504-5 (actual carry-in for first bit used to select between dummy sums generated for subsequent bits).
Although the foregoing designs do increase processing speeds by minimizing wait states, they still do not provide optimum results by minimizing all the wait states that naturally occur. At the same time, most of the prior art techniques use AND/OR circuitry to generate the sum and carry terms, rather than NAND/NOR techniques that minimize device counts and eliminate delays by deleting inverter stages (see U.S. Pat. No. 4,766,565 for an example of ALU design utilizing NAND/NOR techniques).
Accordingly, a need has arisen in the art for a logic synthesis network that further minimizes all wait states inherent in generating sum and carry bits, while utilizing circuit techniques that minimizes device counts and maximize signal generation speeds.